package swordoffer.offer45;

public class QuickSort {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        // 1. 转换成字符串数组
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        // 2. 使用快速排序
        quickSort(strs, 0, strs.length - 1);
        // 3. 拼接
        StringBuilder res = new StringBuilder();
        for (String str : strs) {
            res.append(str);
        }
        return res.toString();
    }
    public void quickSort(String[] strs, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int pivotIndex = partition(strs, lo, hi);
        quickSort(strs, lo, pivotIndex - 1);
        quickSort(strs, pivotIndex + 1, hi);
    }
    public int partition(String[] strs, int lo, int hi) {
        String pivot = strs[lo];
        int left = lo;
        int right = hi;
        while (left < right) {
            // 过滤掉已经符合排序规则的字符
            while (left < right && (strs[right] + pivot).compareTo(pivot + strs[right]) >= 0) {
                right--;
            }
            // 过滤掉已经符合排序规则的字符
            while (left < right && (strs[left] + pivot).compareTo(pivot + strs[left]) <= 0) {
                left++;
            }
            if (left < right) {
                String temp = strs[left];
                strs[left] = strs[right];
                strs[right] = temp;
            }
        }
        strs[lo] = strs[left];
        strs[left] = pivot;
        return left;
    }
}
